// Copyright 2012 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package heap implements functions for sorting integers in an array.
package sort

import "math"

// Implementation of selection sort
func SelectionSort(a []int) {
	var min int
	for i := 0; i < len(a)-1; i++ {
		min = i
		for j := i + 1; j < len(a); j++ {
			if a[j] < a[min] {
				min = j
			}
		}
		if i != min {
			t := a[i]
			a[i] = a[min]
			a[min] = t
		}
	}
}

// Implementation of Insertion Sort in CLRS Chapter 2.1.
func Insertion(a []int) {
	for i := 1; i < len(a); i++ {
		k := a[i]
		j := i - 1
		for ; j >= 0; j-- {
			if a[j] < k {
				break
			}
			a[j+1] = a[j]
		}
		a[j+1] = k
	}
}

// Implementation of Merge in CLRS Chapter 2.3.
func Merge(a []int, p, q, r int) {
	n := q - p + 1
	m := r - q
	L := make([]int, n+1)
	R := make([]int, m+1)
	for i := 0; i < n; i++ {
		L[i] = a[p+i]
	}
	L[n] = (1 << 31) - 1 //Max 32bit int
	z := q + 1
	for i := 0; i < m; i++ {
		R[i] = a[z+i]
	}
	R[m] = (1 << 31) - 1
	x := 0
	y := 0
	for i := p; i <= r; i++ {
		if L[x] < R[y] {
			a[i] = L[x]
			x++
		} else {
			a[i] = R[y]
			y++
		}
	}
}

// Implementation of MergeSort in CLRS Chapter 2.3.
func MergeSort(a []int, p, r int) {
	if p < r {
		q := (p + r) / 2
		MergeSort(a, p, q)
		MergeSort(a, q+1, r)
		Merge(a, p, q, r)
	}
}

// Implementation of Quicksort in CLRS Chapter 7.1.
func Quicksort(a []int, p, r int) {
	if p < r {
		q := Partition(a, p, r)
		Quicksort(a, p, q-1)
		Quicksort(a, q+1, r)
	}
}

// Implementation of Partition in CLRS Chapter 7.1.
func Partition(a []int, p, r int) int {
	i := p - 1
	for j := p; j < r; j++ {
		if a[j] < a[r] {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	i++
	a[r], a[i] = a[i], a[r]
	return i
}

// An implementation of counting sort.
func CountingSort(a []int, m int) []int {
	c := make([]int, m+1)
	l := len(a)
	for i := 0; i < l; i++ {
		c[a[i]]++
	}
	for i := 1; i <= m; i++ {
		c[i] = c[i] + c[i-1]
	}
	b := make([]int, l)
	for i := l - 1; i >= 0; i-- {
		b[c[a[i]]-1] = a[i]
		c[a[i]]--
	}
	return b
}

// An implementation of Radix sort on the dth lowest order digits based on
// CLRS 8.3.  Because of the way that we access digits in Go this is a very
// strange bird.
func RadixSort(a []int, d int) []int {
	w := a // working copy
	l := len(w)
	for i := 1; i <= d; i++ {
		t := make([]int, l) // can save this space
		c := make([]int, 10)
		m := int(math.Pow10(i))
		n := int(math.Pow10(i - 1))
		for j := 0; j < l; j++ {
			t[j] = (w[j] % m) / n
			c[t[j]]++
		}
		for j := 1; j < 10; j++ {
			c[j] = c[j] + c[j-1]
		}
		b := make([]int, l)
		for j := l - 1; j >= 0; j-- {
			b[c[t[j]]-1] = w[j] // by recomputing t[j] here
			c[t[j]]--
		}
		w = b
	}
	return w
}

// An implementation of the general select from CLRS 9.2 (aka Quickfind).
// Here once the nth element is found the elements before the nth element are
// the first least elements.  If you need the largest elements then call this
// asking for the (k-n)th element and the larger elements will be above it.
func QuickFind(a []int, p, r, n int) int {
	if p == r {
		return a[p]
	}
	q := Partition(a, p, r)
	if q == n-1 {
		return a[q]
	}
	if q > n-1 {
		return QuickFind(a, p, q-1, n)
	}
	return QuickFind(a, q+1, r, n)
}
